/*
 * @lc app=leetcode.cn id=面试题 16.25 lang=golang
 * @lcpr version=30118
 *
 * [面试题 16.25] LRU 缓存
 */

// @lcpr-template-start
// package main

// import "fmt"

// func main() {
// 	lru := Constructor(2)
// 	lru.Put(1, 1)
// 	lru.Put(2, 2)
// 	fmt.Println(lru.Get(1))
// 	lru.Put(3, 3)
// 	fmt.Println(lru.Get(2))
// 	lru.Put(4, 4)
// 	fmt.Println(lru.Get(1))
// 	fmt.Println(lru.Get(3))
// 	fmt.Println(lru.Get(4))
// }

// @lcpr-template-end
// @lc code=start

type Node struct {
	Key  int
	Val  int
	Next *Node
	Pre  *Node
}

type LRUCache struct {
	Capacity int
	Head     *Node
	M        map[int]*Node
}

func Constructor(capacity int) LRUCache {
	Head := &Node{}
	Head.Next = Head
	Head.Pre = Head
	return LRUCache{Capacity: capacity, Head: Head, M: make(map[int]*Node)}
}

func (this *LRUCache) Get(key int) int {
	// fmt.Println("查询节点", key)
	// fmt.Println(this.M)
	if node, ok := this.M[key]; ok {
		if node != this.Head.Next {
			this.removeNode(node)
			this.insertHead(node)
		}
		return node.Val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if this.M == nil {
		this.M = make(map[int]*Node)
	}
	// fmt.Println("插入节点", key, value)
	if node, ok := this.M[key]; ok {
		node.Val = value
		if node != this.Head.Next {
			this.removeNode(node)
			this.insertHead(node)
		}
	} else {
		node := &Node{Key: key, Val: value}
		this.M[key] = node
		this.insertHead(node)
		if len(this.M) > this.Capacity { // 超出容量
			// fmt.Println("删除节点", this.Head.Pre.Key)
			delete(this.M, this.Head.Pre.Key)
			this.removeNode(this.Head.Pre)
		}
	}
}

func (this *LRUCache) removeNode(node *Node) {
	next, prev := node.Next, node.Pre
	next.Pre = prev
	prev.Next = next
}

func (this *LRUCache) insertHead(node *Node) {
	if this.Head.Next == this.Head {
		this.Head.Pre = node
		this.Head.Next = node
		node.Pre = this.Head
		node.Next = this.Head
	} else {
		next := this.Head.Next
		next.Pre = node
		node.Pre = this.Head
		node.Next = next
		this.Head.Next = node
	}
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
// @lc code=end
